/**
 * Copyright (c) 2020-2024, huli.com
 * All rights reserved.
 */
package com.xiaohujr.xuexue.leetcode.tree;

/**
 * @author Xue Xue (xuexue1@huli.com)
 * @version 1.0
 * @since 2020/12/11
 */
public class Q110 {
    //自顶向下
    public boolean isBalancedA(TreeNode root) {
        if (root == null) {
            return true;
        }
        return Math.abs(this.heightA(root.left) - this.heightA(root.right)) <= 1 && isBalancedA(root.left) && isBalancedA(root.right);
    }

    public int heightA(TreeNode root) {
        if (root == null) {
            return 0;
        } else {
            return Math.max(heightA(root.left), heightA(root.right)) + 1;
        }
    }

    //自底向上
    public boolean isBalancedB(TreeNode root) {
        return heightB(root) >= 0;
    }

    public int heightB(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftHeight = heightB(root.left);
        int rightHeight = heightB(root.right);
        if (leftHeight == -1 || rightHeight == -1 || Math.abs(leftHeight - rightHeight) > 1) {
            return -1;
        } else {
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }

}
